package com.wm.algorithm.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName: DifficultyBinaryTree
 * @Description: 困难级别
 * @Author: Deamer
 * @Date: 2022/6/4 22:52
 **/
public class DifficultyBinaryTree {

    /**
     * 297. 二叉树的序列化与反序列化
     * (层序遍历)
     * https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
     *
     * @param root
     * @return
     */

    /**
     * 方法：一次遍历
     * 思路：按照层序遍历的写法，把对空指针的检验从「将元素加入队列」的时候改成了「从队列取出元素」的时候，也就是对左右子树
     * 判断是否为空的逻辑改到判断当前取出节点，为空处追加null字符串
     *
     * @param root
     * @return
     */
    // O(height)/O(n)
    // Encodes a tree to a single string.
    /* 主函数，将二叉树序列化为字符串 */
    public String serialize3(TreeNode root) {
        StringBuilder stb = new StringBuilder();
        // 初始化队列，将 root 加入队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            /* 层级遍历代码位置 */
            if (node == null) {
                stb.append("null").append(",");
                continue;
            }
            stb.append(node.val).append(",");
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return stb.toString();
    }


    /**
     * 方法：一次遍历
     * 思路：先找到字符串数组第一个元素就是根节点，后面依次是左右子节点相邻出现，即使为空也是"null"，然后将根节点加入队列中，
     * 遍历余下的元素，将有值的左右子节点加入队列，依次遍历
     * 【用队列进行层级遍历，同时用索引 i 记录对应子节点的位置】
     *
     * @param data
     * @return
     */
    // O(n)/O(n)
    // Decodes your encoded data to tree.
    /* 主函数，将字符串反序列化为二叉树结构 */
    public TreeNode deserialize3(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] nodes = data.split(",");
        // / 第一个元素就是 root 的值，一定要加校验
        if ("null".equals(nodes[0])) {
            return null;
        }
        // 根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        // 队列queue记录父节点，将 root 加入队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 谨记
        for (int i = 1; i < nodes.length; ) {
            // 队列中存的都是父节点
            TreeNode parent = queue.poll();
            // 父节点对应的左侧子节点的值
            String leftVal = nodes[i++];
            if (!"null".equals(leftVal)) {
                parent.left = new TreeNode(Integer.parseInt(leftVal));
                queue.offer(parent.left);
            } else {
                parent.left = null;
            }
            // 父节点对应的右侧子节点的值
            String rightVal = nodes[i++];
            if (!"null".equals(rightVal)) {
                parent.right = new TreeNode(Integer.parseInt(rightVal));
                queue.offer(parent.right);
            } else {
                parent.right = null;
            }
        }
        return root;
    }


    /**
     * 297. 二叉树的序列化与反序列化
     * (后序遍历)
     * https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
     *
     * @param root
     * @return
     */
    // O(height)/O(n)
    // Encodes a tree to a single string.
    /* 主函数，将二叉树序列化为字符串 */
    public String serialize2(TreeNode root) {
        StringBuilder stb = new StringBuilder();
        serialize2(root, stb);
        return stb.toString();
    }

    /* 辅助函数，将二叉树存入 StringBuilder */
    private void serialize2(TreeNode root, StringBuilder stb) {
        if (root == null) {
            stb.append("null").append(",");
            return;
        }
        serialize2(root.left, stb);
        serialize2(root.right, stb);
        /****** 后序遍历位置 ******/
        stb.append(root.val).append(",");
    }


    /**
     * 方法：分解法
     * 思路：root 的值是列表的最后一个元素。从后往前取出列表元素，先用最后一个元素构造 root，
     * 然后递归调用生成 root 的左右子树。注意，从后往前在 nodes 列表中取元素，一定要先构造 root.right 子树，
     * 后构造 root.left 子树
     *
     * @param data
     * @return
     */
    // O(n)/O(n)
    // Decodes your encoded data to tree.
    /* 主函数，将字符串反序列化为二叉树结构 */
    public TreeNode deserialize2(String data) {
        // 将字符串转化成列表
        LinkedList<String> nodes = new LinkedList<>();
        for (String node : data.split(",")) {
            nodes.add(node);
        }
        return deserialize2(nodes);
    }

    /* 辅助函数，通过 nodes 列表构造二叉树 */
    private TreeNode deserialize2(LinkedList<String> nodes) {
        if (nodes.isEmpty()) {
            return null;
        }
        String node = nodes.removeLast();
        if ("null".equals(node)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(node));
        // 注意先构建右子树，再构建左子树
        root.right = deserialize2(nodes);
        root.left = deserialize2(nodes);
        return root;
    }


    /**
     * 297. 二叉树的序列化与反序列化
     * (前序遍历)
     * https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
     *
     * @param root
     * @return
     */

    /**
     * 方法：一次遍历
     * 思路：使用前序遍历的一次遍历解决，注意追加null的情况
     *
     * @param root
     * @return
     */
    // O(height)/O(n)
    // Encodes a tree to a single string.
    /* 主函数，将二叉树序列化为字符串 */
    public String serialize(TreeNode root) {
        StringBuilder stb = new StringBuilder();
        serialize(root, stb);
        return stb.toString();

    }

    /* 辅助函数，将二叉树存入 StringBuilder */
    private void serialize(TreeNode root, StringBuilder stb) {
        if (root == null) {
            stb.append("null").append(",");
            return;
        }
        /****** 前序遍历位置 ******/
        stb.append(root.val).append(",");
        serialize(root.left, stb);
        serialize(root.right, stb);
    }

    /**
     * 方法：分解法
     * 思路：将字符串中的数字元素存储在链表中，先确定根节点，然后通过分解法，根据前序遍历找到左右子树
     *
     * @param data
     * @return
     */
    // O(n)/O(n)
    // Decodes your encoded data to tree.
    /* 主函数，将字符串反序列化为二叉树结构 */
    public TreeNode deserialize(String data) {
        // 将字符串转化成列表
        LinkedList<String> nodes = new LinkedList<>();
        for (String node : data.split(",")) {
            nodes.add(node);
        }
        return deserialize(nodes);
    }

    /* 辅助函数，通过 nodes 列表构造二叉树 */
    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) {
            return null;
        }
        /****** 前序遍历位置 ******/
        // 列表最左侧就是根节点
        String rootVal = nodes.removeFirst();
        if (rootVal.equals("null")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }

    /**
     * 1373. 二叉搜索子树的最大键值和
     * https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/?show=1
     * 方法：一次遍历+后续位置
     * 思路：1、左右子树是否是 BST；2、左子树的最大值和右子树的最小值；3、左右子树的节点值之和。
     *
     * @param root
     * @return
     */
    // 全局变量，记录 BST 最大节点之和
    int maxSum = 0;

    // O(n)/O(height)
    public int maxSumBST(TreeNode root) {
        traverse(root);
        return maxSum;
    }

    private int[] traverse(TreeNode root) {
        if (root == null) {
            // 注意此处，子节点之和的最小值为Integer.MAX_VALUE，最大值为Integer.MIN_VALUE，目的是
            // 让叶子节点可以满足条件更新数数组
            return new int[]{
                    1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0
            };
        }
        // 递归计算左右子树
        int[] left = traverse(root.left);
        int[] right = traverse(root.right);
        // 后续位置
        int[] res = new int[4];
        // 这个 if 在判断以 root 为根的二叉树是不是 BST
        if (left[0] == 1 && right[0] == 1 && root.val > left[2] && root.val < right[1]) {
            // 以 root 为根的二叉树是 BST
            res[0] = 1;
            // 计算以 root 为根的这棵 BST 的最小值
            res[1] = Math.min(root.val, left[1]);
            // 计算以 root 为根的这棵 BST 的最大值
            res[2] = Math.max(root.val, right[2]);
            // 计算以 root 为根的这棵 BST 所有节点之和
            res[3] = root.val + left[3] + right[3];
            // 更新全局变量
            maxSum = Math.max(maxSum, res[3]);
        } else {
            // 以 root 为根的二叉树不是 BST
            res[0] = 0;
            // 其他的值都没必要计算了，因为用不到
        }
        return res;
    }
}
